1. Field of The Invention
This invention generally relates to a circuit for calculating the sum of products of data (hereunder sometimes referred to simply as a sum-of-products calculating circuit) for use in filtering, a matricial operation such as matrix multiplication and so on and more particularly to a sum-of-products calculating circuit having pipeline structure in which a multiplier and an adder are provided and two parallel outputs of a two-output multiplier are written into registers for the purpose of achieving high speed processing, which circuit can equalize the number of bits used for representing output data of the multiplier with that of bits used for representing input data of the adder. 2. Description of The Related Art
First, the construction of a conventional sum-of-products calculating device will be described hereinbelow. FIG. 5 shows the construction of a first example of the conventional sum-of-products calculating device. In this figure, reference numerals 505 and 506 are registers for storing two multiplication input data; 507 a pipeline register for writing multiplication output data therein; 508 a register for storing addition input data; and 509 a register for storing sum output data. Further, reference numeral 501 indicates a partial product generating portion for generating a partial product from the two multiplication input data; 502 a plurality of stages of a Wallace Tree for obtaining two data by performing the addition of the partial products generated by the partial product generating portion 501; and 503 a carry propagation adder (CPS) for obtaining multiplication output data by performing the addition of the two resultant data obtained by performing the addition of the plurality of the stages of the Wallace Tree 502. Morever, reference numeral 504 denotes a CPA for effecting the addition of the multiplication output data 507 and the addition input data 508. In case where a multiplier is constructed by employing a parallel system such as the Wallace Tree, a process of obtaining an output of a multiplier is comprised of the step of obtaining the two output data by using the plurality of the stages of the Wallace Tree 502 from the partial products generated by the partial product generating portion 501 and the step of obtaining the output of the multiplier by performing the addition of the two outputs of the Wallace Tree by using the CPA 503. Further, in case where the bit length of the output data of the multiplier is nearly equal to that of the output of the CPA 503, the multiplication output and the addition input data are added to each other by effecting an operation of substantially the same extent as of the operation effected in the step of obtaining the output of the multiplier by performing the addition of the two outputs of the Wallace Tree. In case of using the configuration of FIG. 5, there is no (or little) difference between the operation time spent in the multiplication step of obtaining the two output data by using the plurality of stages of the Wallace Tree 502 and the CPA 503 and that spent in the addition step of obtaining the output of the multiplier by using the CPA 504. Thus, the performance is deteriorated, considering that the operation is effected by using a pipeline. Accordingly, by employing the sum-of-products calculating device as shown in FIG. 6, an increase of the efficiency of the pipeline processing is intended (see the Japanese Patent Application Provisional Publication No. 1-201771 official gazette "Sum of Products Calculating Device")). In FIG. 6, reference numerals 605 and 606 denote registers for storing the two multiplication input data; 607 and 608 are pipeline registers for writing two intermediate results of the multiplication thereinto; 609 is register for storing addition input data; and 610 is a register for storing addition output data. Further, reference numeral 601 indicates a partial product generating portion for generating a partial product from the two multiplication input data; 602 denotes a plurality of stages of a Wallace Tree for obtaining two data by performing the addition of the partial products generated by the partial product generating portion 601; 603 is another Wallace Tree composed of a single stage for obtaining two outputs from the two intermediate results 607 and 608 and the addition input data 609; and 604 is a carry propagation adder (CPA) for performing the addition of the two outputs of the stage of the Wallace Tree 603. In case of using the configuration of FIG. 6, the operation time spent by the partial product generating portion 601 and the plurality of stages of the Wallace Tree 602 comes to be nearly equal to that spent by the single stage of the Wallace Tree 603 and the CPA 604. Thereby, the performance of the pipeline is improved.
Further, in performing an operation of calculating sum of products, an overflow occurs by adding the results of the multiplication to each other. In order to prevent the overflow, the bit width of data processed by the adder is made larger than that of data processed by the multiplier. This results in the inconsistency of the bit width between the multiplier and the adder. Therefore, the bit width should be extended prior to the addition of the results of the multiplication.
As a conventional bit extension system employed in the sum-of-products calculating device of FIG. 6, a method has been proposed, for example, in which the bit width of the input data to the multiplier is preliminarily extended as dummy data such that the bit width of the two output data of the multiplier is made equal to that of data processed by the adder.
FIG. 7 is a diagram for illustrating an example of this conventional bit extension system. In this example, each multiplication input data to the multiplier is represented by using 4 bits (including a sign bit), and the multiplication of such input data is represented in the form "4-bit data.times.4-bit data", for example, a.sub.3 a.sub.2 a.sub.1 a.sub.0 .times.b.sub.3 b.sub.2 b.sub.1 b.sub.0. Further, data processed by the adder is represented by using 10 bits (including a sign bit), and addition input data is denoted by, for instance, c.sub.9 c.sub.8 c.sub.7 c.sub.6 c.sub.5 c.sub.4 c.sub.3 c.sub.2 c.sub.1 c.sub.0. Morever, in order to perform the bit extension, the sign bit a.sub.3 of the left term (i.e. the multiplicand) is extended to the left side thereof, and the extended bits are regarded as dummy data. Thus, the result of the above described example of the multiplication is obtained by performing the equation a.sub.3 a.sub.3 a.sub.3 a.sub.3 a.sub.2 a.sub.l a.sub.0 .times.b.sub.3 b.sub. 2 b.sub.1 b.sub.0. Furthermore, each stage of the Wallace Tree is constructed by using a full adder in case where the number of data enclosed by an ellipse therein in FIG. 7 is 3 and by using a half adder in case where the number of data enclosed by an ellipse in 2 and sends the result of the operation effected therein to the next stage. The construction of the partial products in FIG. 7 is that of the system known as the Baugh-Wooleys' system of multiplying two's complements. In FIG. 7, the symbol .sup.- is used for indicating an inverted number, and the expression "a.sub.3 OR b.sub.3 " indicates the logical OR between numbers a.sub.3 and b.sub.3. Incidentally, in the calculation illustrated by FIG. 7, is utilized the fact that an expression a.sub.3+b3+a3.b.sub.3 corresponds to an operation "a.sub.3 OR b.sub.3 ". Further, in each stage of the Wallace Tree of FIG. 7, reference character S denotes a sum output of the full adder or of the half adder in the preceding stage thereof and reference character C denotes a carry outputted from the preceding stage thereof. In case of this example, the multiplier comes to obtain the two intermediate results at the third stage of the Wallace Tree thereof, and further, after the two intermediate results are written into the pipeline registers 607 and 608, the addition of these intermediate results and the 10- bit addition input c.sub.9 c.sub.8 c.sub.7 c.sub.6 c.sub.5 c.sub.4 c.sub.3 c.sub.2 c.sub.1 c.sub.0 is effected by using the single stage of the Wallace Tree 603 and the CPA 604.
This conventional system, however, requires 12 full adders and 13 half adders provided in the plurality of stage of the Wallace Tree 602, as well as 16 registers used as pipeline registers, for generating the extended bits which represent dummy data. Thus, this conventional system needs a large number of component elements.
The present invention is provided to eliminate the drawbacks of the conventional system.
It is therefore an object of the present invention to provide a sum-of-products calculating circuit having a bit extension circuit which can reduce the number of component elements.